package com.cxf.windex.base.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author chenxf
 * @date 4/17/2018
 * @description
 */
public class TestUtil {

  private  List<Integer> bags;

  //集合上限
  private  int limitNum;

  //最优集合元素
  private List<Integer> bestSolution;

  private List<Integer> restSolution;

  //最优集合
  private int[][] bestValues;

  private int bestValue;

  //集合数量
  private int n;

  public TestUtil( List<Integer> bags, int limitNum) {
    this.bags = bags;
   // this.limitNum = limitNum;
    this.n = bags.size();
    if (bestValues == null) {
      bestValues = new int[n+1][limitNum+1];
    }
  }
  public void solve() {

    System.out.println("给定背包：");
    for(int b: bags) {
      System.out.println(b);
      limitNum+=b;
    }
    limitNum=limitNum/2;
    System.out.println("给定总承重: " + limitNum);

    // 求解最优值
    for (int j = 0; j <= limitNum; j++) {
      for (int i = 0; i <= n; i++) {
        if (i == 0 || j == 0) {
          bestValues[i][j] = 0;
        }
        else
        {
          // 如果第 i 个背包重量大于总承重，则最优解存在于前 i-1 个背包中，
          // 注意：第 i 个背包是 bags[i-1]
          if (j < bags.get(i-1)) {
            bestValues[i][j] = bestValues[i-1][j];
          }
          else
          {
            // 如果第 i 个背包不大于总承重，则最优解要么是包含第 i 个背包的最优解，
            // 要么是不包含第 i 个背包的最优解， 取两者最大值，这里采用了分类讨论法
            // 第 i 个背包的重量 iweight 和价值 ivalue
            int iweight =  bags.get(i-1);
            int ivalue =  bags.get(i-1);
            bestValues[i][j] =
                Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);
          } // else
        } //else
      } //for
    } //for

    // 求解背包组成
    if (bestSolution == null) {
      bestSolution = new ArrayList<Integer>();
      restSolution=new  ArrayList<Integer>();
    }
    int tempWeight = limitNum;
    for (int i=n; i >= 1; i--) {
      if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {
        bestSolution.add( bags.get(i-1));  // bags[i-1] 表示第 i 个背包
        tempWeight -= bags.get(i-1);
      }
      if (tempWeight == 0) { break; }
    }

    restSolution=bags.stream().filter(value -> !bestSolution.contains(value)).collect(
        Collectors.toList());
    bestValue = bestValues[n][limitNum];
  }

  public List<Integer> getBags() {
    return bags;
  }

  public void setBags(List<Integer> bags) {
    this.bags = bags;
  }

  public void setBestSolution(List<Integer> bestSolution) {
    this.bestSolution = bestSolution;
  }

  public void setRestSolution(List<Integer> restSolution) {
    this.restSolution = restSolution;
  }

  public int getLimitNum() {
    return limitNum;
  }

  public void setLimitNum(int limitNum) {
    this.limitNum = limitNum;
  }

  public List<Integer> getBestSolution() {
    return bestSolution;
  }

  public void setBestSolution(ArrayList<Integer> bestSolution) {
    this.bestSolution = bestSolution;
  }

  public int[][] getBestValues() {
    return bestValues;
  }

  public void setBestValues(int[][] bestValues) {
    this.bestValues = bestValues;
  }

  public int getN() {
    return n;
  }

  public void setN(int n) {
    this.n = n;
  }

  public int getBestValue() {
    return bestValue;
  }

  public void setBestValue(int bestValue) {
    this.bestValue = bestValue;
  }

  public List<Integer> getRestSolution() {
    return restSolution;
  }

  public void setRestSolution(ArrayList<Integer> restSolution) {
    this.restSolution = restSolution;
  }

  public static void main(String[] args) {
    TestUtil kp=new TestUtil(Arrays.asList(100),2016);
    kp.solve();
    // TODO Auto-generated method stub
    System.out.println(" -------- 该背包问题实例的解: --------- ");
    System.out.println("最优值：" + kp.getBestValue());
    System.out.println("最优解【选取的背包】: ");
    System.out.println(kp.getBestSolution());
    System.out.println("剩下的【选取的背包】: ");
    System.out.println(kp.getRestSolution());
    System.out.println("最优值矩阵：");
    List<Integer> bestValues = kp.getBestSolution();
    for (Integer i:bestValues) {
        System.out.printf("%-5d", i);
      System.out.println();
    }
  }


}
